package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test
import xyz.scootaloo.common.TestDsl

/**
 * @update 2021/7/3 8:53
 *
 * @author flutterdash@qq.com
 * @since 2021/4/28 15:44
 */
class P189 : TestDsl {

    /**
     * 解法1:
     * 使用临时数组拷贝
     * 以 k 为中点
     * 将原数组 k 之后的元素数拷贝到临时数组的 前k个
     * 将原数组 k 之前的元素拷贝到临时数组的 后k个
     *
     * 步骤 (k = 3):
     * 1. nums=[1, 2, 3, 4, 5, 6, 7]  tmp=[ ,  ,  ,  ,  ,  ,  ] 创建和nums一样大小的的临时数组
     * 2.                             tmp=[ ,  ,  , 1, 2, 3, 4]
     * 3.                             tmp=[5, 6, 7, 1, 2, 3, 4]
     * 4. nums=[5, 6, 7, 1, 2, 3, 4]  tmp=[5, 6, 7, 1, 2, 3, 4] 将处理完成后的临时数组的结果拷贝回原数组
     */
    fun rotate(nums: IntArray, k: Int): Unit {
        rotateCore(nums, k % nums.size)
    }

    private fun rotateCore(nums: IntArray, k: Int) {
        val tmpArr = IntArray(nums.size)
        val mid = nums.size - k
        for (i in 0 until mid)
            tmpArr[i + k] = nums[i]
        for (i in mid until nums.size)
            tmpArr[i - mid] = nums[i]
        for (i in nums.indices)
            nums[i] = tmpArr[i]
    }

    @Test
    fun test0() {
        val input0 = intArrayOf(1, 2, 3, 4, 5, 6, 7)
        rotate(input0, 3)
        Console.log(input0)
    }

    /**
     * 解法二:
     * step0. [1,2,3,4,5,6,7]
     * step1. [7,6,5,4,3,2,1]
     * step2. [5,6,7,4,3,2,1]
     * step3. [5,6,7,1,2,3,4]
     */
    fun newRotate(nums: IntArray, k: Int) {
        val mid = k % nums.size
        reverse(nums, 0, nums.size - 1)
        reverse(nums, 0, mid - 1)
        reverse(nums, mid, nums.size - 1)
    }

    private fun reverse(nums: IntArray, left: Int, right: Int) {
        var l = left
        var r = right
        var tmp: Int
        while (l < r) {
            tmp = nums[l]
            nums[l] = nums[r]
            nums[r] = tmp
            l++
            r--
        }
    }

    @Test
    fun test1() {
        val input0 = intArrayOf(1, 2, 3, 4, 5, 6, 7)
        newRotate(input0, 3)
        Console.log(input0)
    }

    /**
     * nums = [1, 2, 3, 4, 5, 6, 7], k = 3
     *         -  -  -  >  -  -  >   ==> - - > - - - >
     *         <  -  -  <  -  -  -
     *         -  -  >  -  -  -  >
     */
    fun rotate0(nums: IntArray, k: Int): Unit {
        fun reverse0(from: Int, to: Int) {
            var left = from
            var right = to
            var tmp: Int
            while (left < right) {
                tmp = nums[left]
                nums[left] = nums[right]
                nums[right] = tmp
                left++
                right--
            }
        }

        val size = nums.size - 1
        val pivot = k % nums.size
        reverse0(0, size)
        reverse0(0, pivot - 1)
        reverse0(pivot, size)
    }

    @Test
    fun test2() {
        val input0 = intArrayOf(1, 2, 3, 4, 5, 6, 7)
        rotate0(input0, 3)
        input0.log()
    }

}
